package leetcode.code1155;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;


//执行用时：10 ms, 在所有 Java 提交中击败了80.37%的用户
//
//内存消耗：40.7 MB, 在所有 Java 提交中击败了5.05%的用户
//
//通过测试用例：65 / 65
public class Solution2 implements IDebug {

	int k;

	final int mod = (int) 1e9 + 7;

	public int numRollsToTarget(int n, int k, int target) {
		this.k = k;
		Integer[][] dp = new Integer[n + 1][target + 1];
		return this.f(n, target, dp);
	}

	private int f(int n, int target, Integer[][] dp) {
		if (n == 0 && target == 0) {
			return 1;
		}
		if (n <= 0 || target <= 0) {
			return 0;
		}
		if (dp[n][target] != null) {
			return dp[n][target];
		}
		int ans = 0;
		for (int i = 1; i <= this.k; i++) {
			ans += this.f(n - 1, target - i, dp);
			ans %= mod;
		}
		dp[n][target] = ans;
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(1, this.numRollsToTarget(1, 6, 3));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(6, this.numRollsToTarget(2, 6, 7));

	}

	@Override
	public void debug3() {
		HelpDebug.compare(1, this.numRollsToTarget(2, 5, 10));

	}

	@Override
	public void debug4() {

		HelpDebug.compare(222616187, this.numRollsToTarget(30, 30, 500));
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
